﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Serialization;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp2
{
    
    public class DoubleLinkedListNode<T>
    {
        LinkedList<int> vs;
        public DoubleLinkedListNode(T value, DoubleLinkedListNode<T> pre = null, DoubleLinkedListNode<T> next = null, DoubleLinkedList<T> list = null)
        {
            this.Value = value;
            this.Previous = pre;
            this.Next = next;
            this.List = list;
        }

        public DoubleLinkedList<T> List { get; set; }
        public DoubleLinkedListNode<T> Next { get; set; }
        public DoubleLinkedListNode<T> Previous { get; set; }
        public T Value { get; set; }
    }
    public class DoubleLinkedList<T> : IEnumerable<T>
    {
        private DoubleLinkedListNode<T> _last;//最后一个
        private DoubleLinkedListNode<T> _first;//第一个
        private int _count;
        public DoubleLinkedListNode<T> Last => _last;
        public DoubleLinkedListNode<T> First => _first;
        public int Count => _count;

        public DoubleLinkedListNode<T> AddAfter(DoubleLinkedListNode<T> node, T value)
        {
            if (node == null)
            {
                throw new ArgumentNullException("不能插入空节点之后!");
            }
            if (node.List != this)
            {
                throw new InvalidOperationException("被插入的结点不属于本链表!");
            }
            DoubleLinkedListNode<T> newNode= new DoubleLinkedListNode<T>(value, node, node.Next, this);
            if (node == _last)
            {
                _last = newNode;
            }
            if (node.Next != null)
            {
                node.Next.Previous = newNode;
            }
            node.Next = newNode;
            _count++;
            return newNode;
        }
        public void AddAfter(DoubleLinkedListNode<T> node, DoubleLinkedListNode<T> newNode)
        {
            if (node == null || newNode == null)
            {
                throw new ArgumentNullException("不能插入空节点之后或插入空节点!");
            }
            if (node == newNode)
            {
                throw new Exception("不能自己插入自己之后!");
            }
            if (node.List != this || (newNode.List != null && newNode.List != this))
            {
                throw new InvalidOperationException("被插入的结点不属于本链表或插入结点属于别的链表!");
            }
            if (newNode.List == this)
            {
                Remove(node);
            }
            if (node == _last)
            {
                _last = newNode;
            }
            newNode.Previous = node;
            newNode.Next = node.Next;
            if (node.Next != null)
            {
                node.Next.Previous = newNode;
            }
            node.Next = newNode;
            newNode.List = this;
            _count++;
        }
        public DoubleLinkedListNode<T> AddBefore(DoubleLinkedListNode<T> node, T value)
        {
            if (node == null)
            {
                throw new ArgumentNullException("不能插入空节点之后!");
            }
            if (node.List != this)
            {
                throw new InvalidOperationException("被插入的结点不属于本链表!");
            }
            DoubleLinkedListNode<T> newNode = new DoubleLinkedListNode<T>(value, node.Previous, node, this);
            if (node == _first)
            {
                _first = newNode;
            }
            if (node.Previous != null)
            {
                node.Previous.Next = newNode;
            }
            node.Previous = newNode;
            _count++;
            return newNode;
        }
        public void AddBefore(DoubleLinkedListNode<T> node, DoubleLinkedListNode<T> newNode)
        {
            if (node == null || newNode == null)
            {
                throw new ArgumentNullException("不能插入空节点之后或插入空节点!");
            }
            if (node == newNode)
            {
                throw new Exception("不能自己插入自己之后!");
            }
            if (node.List != this || (newNode.List != null && newNode.List != this))
            {
                throw new InvalidOperationException("被插入的结点不属于本链表或插入结点属于别的链表!");
            }
            if (newNode.List == this)
            {
                Remove(node);
            }
            if (node == _first)
            {
                _first = newNode;
            }
            newNode.Previous = node.Previous;
            newNode.Next = node;
            if (node.Previous != null)
            {
                node.Previous.Next = newNode;
            }
            node.Previous = newNode;
            newNode.List = this;
            _count++;
        }
        public DoubleLinkedListNode<T> AddFirst(T value)
        {
            DoubleLinkedListNode<T> newNode = new DoubleLinkedListNode<T>(value, null, _first, this);
            if (_first == null)
            {
                _first = _last = newNode;
            }
            else
            {
                _first.Previous = newNode;
                _first = newNode;
            }
            _count++;
            return First;
        }
        public void AddFirst(DoubleLinkedListNode<T> node)
        {
            if (node == null)
            {
                throw new ArgumentNullException("不能插入空节点!");
            }
            if (node.List == this)
            {
                Remove(node);
            }
            else if (node.List != null)
            {
                throw new InvalidOperationException("插入结点属于别的链表!");
            }
            if (_first == null)
            {
                _first = _last = node;
            }
            else
            {
                _first.Previous = node;
                node.Next = _first;
                _first = node;
            }
            node.List = this;
            _count++;
        }
        public DoubleLinkedListNode<T> AddLast(T value)
        {
            DoubleLinkedListNode<T> newNode = new DoubleLinkedListNode<T>(value, _last, null, this);
            if (_last == null)
            {
                 _last = newNode;
            }
            else
            {
                _last.Next = newNode;
                _last = newNode;
            }
            _count++;
            return Last;
        }
        public void AddLast(DoubleLinkedListNode<T> node)
        {
            if (node == null)
            {
                throw new ArgumentNullException("不能插入空节点!");
            }
            if (node.List == this)
            {
                Remove(node);
            }
            else if (node.List != null)
            {
                throw new InvalidOperationException("插入结点属于别的链表!");
            }
            if (_last == null)
            {
                _first = _last = node;
            }
            else
            {
                _last.Next = node;
                node.Previous = _last;
                _last = node;
            }
            node.List = this;
            _count++;
        }
        public void Clear()
        {
            _count = 0;
            _first = null;
            _last = null;
        }
        public bool Contains(T value)
        {
            foreach (var item in this)
            {
                if (Comparer<T>.Default.Compare(value, item) == 0)
                {
                    return true;
                }
            }
            return false;
        }
        public void CopyTo(T[] array, int index)
        {
            if (array == null)
            {
                throw new ArgumentNullException("数组为null");
            }
            if (array.Length == 0)
            {
                throw new ArgumentOutOfRangeException("数组长度小于零!");
            }
            if (array.Length - index < Count)
            {
                throw new ArgumentException("数组长度不够用!");
            }
            foreach (var item in this)
            {
                array[index++] = item;
            }
        }
        public DoubleLinkedListNode<T> Find(T value)
        {
            DoubleLinkedListNode<T> node = _first;
            while (node != null)
            {
                if (Comparer<T>.Default.Compare(value, node.Value) == 0)
                {
                    return node;
                }
                node = node.Next;
            }
            return node;
        }
        public DoubleLinkedListNode<T> FindLast(T value)
        {
            DoubleLinkedListNode<T> node = _last;
            while (node != null)
            {
                if (Comparer<T>.Default.Compare(value, node.Value) == 0)
                {
                    return node;
                }
                node = node.Previous;
            }
            return node;
        }

        public IEnumerator<T> GetEnumerator()
        {
            throw new NotImplementedException();
        }

        public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
        {

        }
        public virtual void OnDeserialization(object sender)
        {

        }
        public bool Remove(T value)
        {
            DoubleLinkedListNode<T> node = Find(value);
            if (node == null)
            {
                return false;
            }
            Remove(node);
            return true;
        }
        public void Remove(DoubleLinkedListNode<T> node)
        {
            if (node == null)
            {
                throw new ArgumentNullException("node 为 null");
            }
            if (node.List == this)
            {
                if (node.Previous != null)
                {
                    node.Previous.Next = node.Next;
                }
                if (node.Next != null)
                {
                    node.Next.Previous = node.Previous;
                }
                node.Previous = null;
                node.Next = null;
                node.List = null;
                _count--;
                if (node == _first)
                {
                    _first = null;
                }
                if (node == _last)
                {
                    _last = null;
                }
            }
            else
            {
                throw new InvalidOperationException("node不在当前链表中!");
            }
        }
        public void RemoveFirst()
        {
            if (_first == null)
            {
                throw new InvalidOperationException("链表内容为空!");
            }
            _first = _first.Next;
            _first.Previous = null;
            _count--;
        }
        public void RemoveLast()
        {
            if (_last == null)
            {
                throw new InvalidOperationException("链表内容为空!");
            }
            _last = _last.Previous;
            _last.Next = null;
            _count--;
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            DoubleLinkedListNode<T> node = _first;
            while (node != null)
            {
                yield return node.Value;
                node = node.Next;
            }
        }
    }
}
